#ifndef LEETCODE_CN_CPP_CONTESTS_WEEKLY_180_H
#define LEETCODE_CN_CPP_CONTESTS_WEEKLY_180_H

#include "utils/tree.h"
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

namespace weekly_180
{

namespace problem_5356
{

class Solution
{
public:
    vector<int> luckyNumbers(vector<vector<int>> &matrix)
    {
        vector<int> mins;
        mins.reserve(matrix.size());
        for (const auto &row : matrix)
            mins.push_back(distance(row.begin(), min_element(row.begin(), row.end())));
        vector<int> results;
        results.reserve(matrix.size());
        for (int row = 0; row < matrix.size(); ++row)
        {
            int minCol = mins[row];
            int minVal = matrix[row][minCol];
            bool ok = true;
            for (int i = 0; i < matrix.size(); ++i)
            {
                if (matrix[i][minCol] > minVal)
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
            {
                results.push_back(minVal);
            }
        }
        return move(results);
    }
};

} // namespace problem_5356

namespace problem_5357
{

// class CustomStack
// {
// private:
//     struct __comp
//     {
//         constexpr bool operator()(const pair<int, int> &a, const pair<int, int> &b)
//         {
//             return a.first < b.first;
//         }
//     };

// private:
//     int maxSize;
//     stack<int> stk;
//     priority_queue<pair<int, int>, vector<pair<int, int>>, __comp> increments;

// public:
//     CustomStack(int maxSize) : maxSize(maxSize) {}

//     void push(int x)
//     {
//         if (stk.size() < maxSize)
//             stk.push(x);
//     }

//     int pop()
//     {
//         if (stk.empty())
//         {
//             while (!increments.empty())
//                 increments.pop();
//             return -1;
//         }
//         int k = stk.size();
//         int val = stk.top();
//         stk.pop();
//         unordered_map<int, int> toUpdates;
//         while (!increments.empty() && increments.top().first >= k)
//         {
//             toUpdates[increments.top().first] += increments.top().second;
//             increments.pop();
//         }
//         for (auto &item : toUpdates)
//         {
//             val += item.second;
//             if (item.first > 1)
//             {
//                 increments.emplace(item.first - 1, item.second);
//             }
//         }
//         return val;
//     }

//     void increment(int k, int val)
//     {
//         if (k <= 0 || stk.empty())
//             return;
//         if (k > stk.size())
//             k = stk.size();
//         increments.emplace(k, val);
//     }
// };

// optimized
class CustomStack
{
private:
    struct Node
    {
        int value, increment;
        Node(int value, int increment) : value(value), increment(increment) {}
    };

    int maxSize;
    vector<Node> stk;

public:
    CustomStack(int maxSize) : maxSize(maxSize) {}

    void push(int x)
    {
        if (stk.size() == maxSize)
            return;
        stk.emplace_back(x, 0);
    }

    int pop()
    {
        if (stk.empty())
            return -1;
        int val = stk.back().value;
        int inc = stk.back().increment;
        stk.pop_back();
        if (!stk.empty())
            stk.back().increment += inc;
        return val + inc;
    }

    void increment(int k, int val)
    {
        if (k <= 0 || stk.empty())
            return;
        if (k > stk.size())
            k = stk.size();
        stk[k - 1].increment += val;
    }
};

} // namespace problem_5357

namespace problem_5179
{

class Solution
{
private:
    vector<TreeNode *> nodes;
    void inorder(TreeNode *root)
    {
        if (root == nullptr)
            return;
        inorder(root->left);
        nodes.push_back(root);
        inorder(root->right);
    }
    TreeNode *build(int i, int j)
    {
        if (i > j)
            return nullptr;
        if (i == j)
        {
            nodes[i]->left = nullptr;
            nodes[i]->right = nullptr;
            return nodes[i];
        }
        int mid = i + (j - i) / 2;
        nodes[mid]->left = build(i, mid - 1);
        nodes[mid]->right = build(mid + 1, j);
        return nodes[mid];
    }

public:
    TreeNode *balanceBST(TreeNode *root)
    {
        nodes.clear();
        inorder(root);
        if (nodes.empty())
            return nullptr;
        auto result = build(0, nodes.size() - 1);
        nodes.clear();
        return result;
    }
};

} // namespace problem_5179

namespace problem_5359
{

class Solution
{
public:
    int maxPerformance(int n, vector<int> &speed, vector<int> &efficiency, int k)
    {
        vector<pair<int, int>> engineers;
        engineers.reserve(n);
        for (int i = 0; i < n; ++i)
            engineers.emplace_back(speed[i], efficiency[i]);
        // 按照efficiency从大到小排序
        sort(engineers.begin(), engineers.end(),
             [](const pair<int, int> &a, const pair<int, int> &b) {
                 return a.second > b.second;
             });
        priority_queue<int, vector<int>, greater<int>> pqueue;
        long sum = 0, result = 0;
        for (int i = 0; i < n; ++i)
        {
            // 因为按照eff从大到小排序，所以当第i个员工作为最小的eff时，
            // 只要从[0,i-1]中选出k-1个speed最大的就可以
            long spd = engineers[i].first, eff = engineers[i].second;
            sum += spd;
            // 堆中保存i前面的k-1个最大speed
            if (pqueue.size() == k)
            {
                sum -= pqueue.top();
                pqueue.pop();
            }
            pqueue.push(spd);
            result = max(result, sum * eff);
        }
        return result % 1000000007;
    }
};

} // namespace problem_5359

} // namespace weekly_180

#endif //LEETCODE_CN_CPP_CONTESTS_WEEKLY_180_H
